A communication channel is the medium between a transmitter and a receiver. The medium may introduce noise, interference or other channel errors. Any medium that may inject errors will be referred to as a channel. The medium may be a storage medium or a communication medium. The purpose of channel encoding and decoding is to assist in protecting against channel errors, which occur in situations such as where there is noise, fading, multipath and interference, when signal transmission or reception is in an elevator, in a moving car, amidst tall buildings, in hilly terrain, or the like.
Channel encoding techniques typically involve the addition of redundant bits to the input bit stream to assist in error detection and correction. Channel encoding, which is generally standardized, includes two main techniques: block encoding and convolutional encoding. The present invention is relevant to convolutional encoding.
Convolutional codes differ from block codes in that the encoder contains memory and the “n” encoder outputs at any given time unit rely not only on the “k” inputs at that time unit, but also on “m” previous input blocks. An (n, k, m) convolutional code can be realized with a k-input n-output linear sequential circuit, with “m” memory elements. Convolutional codes have been used extensively in digital communications in order to improve error performance and thereby protect the source information better [Lin, S., Costello, D. J., “Error Control Coding: Fundamentals and Applications”, Englewood Cliffs, N.J.: Prentice-Hall, 1983]. The channel encoder illustrated in FIG. 1 is a convolutional encoder, comprising an input carrying input frames connected to five memory elements 110, which are connect to the inputs of two XOR gates 112, 114 whose outputs are in turn connected to a multiplexor (MUX) 130 whose output is the encoded frame. An (n,k,m) convolutional encoder has 2m states and a rate k/n. The convolutional encoder with m=5 of FIG. 1 has 25 or 32 probable states. Such a rate-1/2 convolutional encoder generates a symbol with two (2) output bits for each input bit. A rate-1/3 convolutional encoder outputs three (3) bits for every input bit, and so on. While it is important to add redundant bits to facilitate error detection and correction, transmission of the redundant bits consumes additional bandwidth. It is therefore important in a given application to use a convolutional encoder with as high a rate as possible while maintaining an acceptable error tolerance for the application.
More sophisticated convolutional encoders generally have more memory, and therefore more states, than less sophisticated ones. The more states a convolutional encoder has, the higher will be the complexity of the decoding process. As the convolutional encoder with m=5 of FIG. 1 has thirty-two (32) states, the decoding process will have fairly high complexity. For a convolutional encoder with seven (7) memory elements, the complexity of the decoding process would be even higher.
In a convolutional encoder, each input bit must travel through each memory element in order for the number of output bits generated by the convolutional encoder to correspond to the number of input bits and the rate of the convolutional encoder. One method of convolutional encoding is to use tail bits to flush the convolutional encoder by initializing each memory element with a zero (0). In other words, the convolutional encoder is forced to reset to the all 0 state by passing through it a string of 0's of length equal to the memory of the convolutional encoder. The input bit stream is increased in length by the number of tail bits. Thus, for the convolutional encoder with m=5 of FIG. 1, five (5) 0's would be added at the end of the input bit stream in order for all input bits to pass through all memory elements 110. Note that the tail bits do not have to be all 0's. They could be all ones (1's), or a known combination of 0's and 1's. What is important is that the values of the tail bits are known at the decoder.
Tail bits are important for ensuring that each input bit passes through each memory element of the convolutional encoder. Furthermore, the decoding process is made easier by virtue of the fact that the initial state, e.g. all 0's, of the encoder is known. However, tail bits use additional bandwidth, since the tail bits must also be passed through the encoder to process each input frame. Thus, a rate-1/2 convolutional encoder will output 270 bits for an input frame consisting of 130 input bits, since 130 input bits plus 5 tail bits must be processed.
In order to conserve bandwidth, it is desirable to reduce the number of output bits generated by a convolutional encoder. To this end, the concepts of tail-biting and puncturing may be applied.
Tail-biting typically involves initializing the m encoder memory elements with the first m input bits in the input bit stream. The first m input bits are also copied to the end of the input bit stream and processed again by the convolutional encoder. Thus, with respect to the convolutional encoder of FIG. 1, input bits b0, b1, b2, b3 and b4 are used for initializing the encoder memory and also are circulated back to the end of the bit stream. Alternatively, the last input bits in the input bit stream may be used to initialize the convolutional encoder and then the entire input bit stream is passed through the encoder to form the output bit stream. In a further alternative, bits from both the beginning and end of the input bit stream may be used to initialize the convolutional encoder. Tail biting codes may be conceived as circular convolutional codes. Thus, any subset of the input bit stream could be used for initializing, the memory elements (with reference to FIG. 1, this would be five (5) memory elements 110), as long as all the bits thereafter pass through the memory elements in a cyclic fashion.
Puncturing derives a higher rate convolutional code from a lower rate convolutional encoder, so that the output bit stream is shorter in length compared to the output bit stream produced without any puncturing. This helps obtain sufficient coding gain without occupying as much bandwidth. In a punctured tail-biting code, the number of symbols in the extension bits used for tail-biting typically corresponds to a whole number of puncture periods. However, at the extension boundary, the puncture period may not be completed. For example, in the above scenario, Glp43, Gr215 form the 216-th symbol (which is non-punctured). The next symbol (after extension) will be Glp0, Gr0, which happens to be non-punctured also. While computing the decoding metric, this needs to be taken into account.
Tail-biting convolutional codes may be low rate (e.g., rate-1/2) or high rate (e.g., rate-5/6). As indicated above, low rate convolutional codes have more redundancy than high rate convolutional codes. High rate convolutional codes may be generated directly or by puncturing a low rate convolutional code. High rate punctured tail-biting convolutional codes are desirable in certain applications. While they have less error detection and correction capability compared to the low rate convolutional code from which they are derived, due to reduced redundancy in the output of the convolutional encoder, they provide higher data rate and are capable of providing, when used in conjunction with Automatic Repeat Request (ARQ) protocol, lower frame error rate (FER).
FIG. 2 illustrates a tail-biting rate-5/6 convolutional channel encoder. This tail-biting coding arrangement initializes the memory 210 with the first five (5) input bits, which are circulated again at the end of the input bit stream. A puncture element 220 derives a rate-5/6 convolutional code from rate-1/2 bit streams Gl and Gr. All bits from output stream Gr are transmitted to a multiplexer (MUX) 230, while only every fifth bit from output stream Gl is transmitted to the MUX 230. Thus, for an input bit stream b of (b0, b1, b2, . . . ), bit streams Gl of (Gl0, Gl1, Gl2, . . . ) and Gr of (Gr0, Gr1, Gr2, . . . ) are generated. Puncture element 220 then generates a bit stream Glp of (Gl0, Gl5, Gl10, . . . ), and MUX 230 generates a bit stream Go of (Glp0, Gr0, Gr1, Gr2, Gr3, Gr4, Glp1, Gr5, Gr6, . . . ). Thus, for every five (5) input bits, only one additional bit is added by the rate-5/6 convolutional encoder compared to five (5) bits added by a rate-1/2 encoder. The reduced error correcting ability of the convolutional code associated with puncturing may be sufficient for an application, may be offset by other forward error correction techniques, and may be compensated for in other ways, such as by defining more states.
Decoding tail-biting convolutional code is significantly more complex than decoding non-tail-biting convolutional code. Although the encoding polynomials are known to the decoder, the initial state of the convolutional encoder is unknown. Sophisticated techniques must therefore be employed by the decoder to estimate the input bit stream from the bit stream received over the channel.
The Viterbi algorithm is typically used to decode non-tail-biting codes [H. H. Ma and J. K. Wolf, “On Tail Biting Convolutional Codes”, IEEE Transactions on Communications, Vol. COM-34, No. 2, pp. 104-111, February 1986; Q. Wang and V. K. Bhargava, “An Efficient Maximum Likelihood Decoding Algorithm for Generalized Tail Biting Convolutional Codes Including Quasicyclic Codes”, IEEE Transactions on Communications., Vol. 37, No. 8, pp. 875-879, August 1989; S. Chennakeshu and R. L. Toy, “Generalized Viterbi Algorithm with Tail-Biting”, U.S. Pat. No. 5,349,589, Issue Date: Sep. 20, 1994]. Note that the Viterbi algorithm is equally applicable to punctured code, provided that the deleted bit pattern is taken into account by the decoding scheme while computing the decoding metric or depuncturing is done before the decoding. For non-tail-biting codes, the Viterbi algorithm has the luxury of assuming that the encoder was in state 0 when the first information was transmitted. With tail-biting codes, this is no longer the case. In fact, for arbitrary data input, the encoder may have started in any of the possible states. FIG. 3 illustrates a simple (but high-complexity) decoding scheme for tail-biting codes could be as follows [H. H. Ma and J. K. Wolf, “On Tail Biting Convolutional Codes”, IEEE Transaction on Communications, Vol. COM-34, No. 2, pp. 104-111, February 1986]:                Receive 305 an input bit stream        Step 1: Assume 310 that the starting state of the encoder was 0.        Step 2: Apply 315 the Viterbi algorithm as usual.        Step 3: Save 320 both the best-trellis-path, and its decoding metric score from Step 2.        Step 4: Assume that the starting state of the encoder was 1, then repeat Steps 2 and 3.        Step 5: Repeat Steps 2 and 3 with all of the remaining states as initial state.        Step 6: Of all paths and scores collected from the runs above, pick the path 335 which had the best decoding metric score 340. The input sequence derived from this path 345 will always be the most likely input.        
The algorithm of FIG. 3 provides an optimal solution, but may be unacceptably slow for many applications. This scheme is unsuitable for real-time application as the code processing complexity is always 2M times that of its non-tail-biting counterpart, where M is the number of memory elements in the encoder [R. V. Cox and C-E. W. Sundberg, “An Efficient Adaptive Circular Viterbi Algorithm for Decoding Generalized Tail-biting Convolutional Codes”, IEEE Transactions on Vehicular Technology, Vol. 43, No. 1, pp. 57-68, February 1994]. With such a scheme, the “starting state=ending state” property of the tail-biting code could be used implicitly or explicitly.
Recently, a number of sub-optimal decoding algorithms have been proposed in order to make the decoder complexity low enough for practical applications. A two (2) step sub-optimum algorithm proposed by Ma and Wolf [H. H. Ma and J. K. Wolf, “On Tail Biting Convolutional Codes”, IEEE Transactions on Communications, Vol. COM-34, No. 2, pp. 104-111, February 1986] is only somewhat simpler than the optimum decoder. For real-time applications, such high complexity (which increases exponentially) techniques are not generally affordable in terms of computational power.
Sub-optimum algorithms proposed by Bar-David [H. H. Ma and J. K. Wolf, “On Tail Biting Convolutional Codes”, IEEE Transactions on Communications, Vol. COM-34, No. 2, pp. 104-111, February 1986] and Wang and Bhargava [Q. Wang and V. K. Bhargava, “An Efficient Maximum Likelihood Decoding Algorithm for Generalized Tail Biting Convolutional Codes Including Quasicyclic Codes”, IEEE Transactions on Communications., Vol. 37, No. 8, pp. 875-879, August 1989], reduce the computational complexity on an average basis. However, at times, they approach the complexity of the optimal decoding algorithm, especially in low and intermediate channel signal-to-noise ratio. Due to involving a variable number of trials, these schemes are not ideal for our implementation where worst-case complexity also has to be reasonable.
U.S. Pat. No. 5,349,589, Issue Date: Sep. 20, 1994; S. Chennakeshu and R. L. Toy, “Generalized Viterbi Algorithm with Tail-Biting”, and U.S. Pat. No. 5,369,671, Issue Date: Nov. 29, 1994; Yehushua, M., Watson, J., and Parr, M., “System and Method for Decoding Tail-Biting Code Especially Applicable to Digital Cellular Base Station and Mobile Units” describe decoding techniques for tail-biting codes. U.S. Pat. No. 5,369,671 describes a method or control message (in quadruple form) decoding, that is not concerned with puncturing, i.e., with high-rate code, that applies pure Viterbi algorithm technique and that assumes a pre-determined starting state. U.S. Pat. No. 5,349,589 describes a method that starts with all the possible states and finds out which one provides the lowest metric (this implies quite high complexity), that applies the Viterbi algorithm and a trace-back technique for bit decisions, and that utilizes the “starting stage=ending stage” property for tail-biting code explicitly.
In addition to hard-decision decoding, there are also soft-decision decoding techniques that can be applied for tail-biting codes. A circular MAP decoder is presented in U.S. Pat. No. 5,721,746. Another efficient adaptive circular Viterbi algorithm using soft-decision decoding is studied in [R. V. Cox and C-E. W. Sundberg, “An Efficient Adaptive Circular Viterbi Algorithm for Decoding Generalized Tailbiting Convolutional Codes”, IEEE Transactions on Vehicular Technology, Vol. 43, No. 1, pp. 57-68, February 1994; Cox, R. V. and Sundberg, C-E. W., “Circular Viterbi Decoder”, U.S. Pat. No. 5,355,376, Issue Date: Oct. 11, 1994].
From the above discussion, it can be seen that there is a need for a sub-optimal channel decoder for decoding both low and high rate tail-biting convolutional codes that is less complex (and therefore computationally less demanding) and yet has error performance close to that of an optimal channel decoder.